HackerRank The Maximum Subarray
https://www.hackerrank.com/challenges/maxsubarray/problem
提出
code: python
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'maxSubarray' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#
def maxSubarray(arr):
# Write your code here
subsequence = 0
for i in arr:
if i > 0:
subsequence += i
if subsequence == 0:
subsequence += max(arr)
cumu = [arr0]
for i in range(1, len(arr)):
cumu.append(arri + cumu-1)
print(cumu)
return subsequence
if __name__ == '__main__':
fptr = open(os.environ'OUTPUT_PATH', 'w')
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = maxSubarray(arr)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
解答
code: python
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'maxSubarray' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#
def maxSubarray(arr):
# Write your code here
subsequence = 0
for i in arr:
if i > 0:
subsequence += i
if subsequence == 0:
subsequence += max(arr)
# Kadane's Algorithm
max_current = max_global = arr0
for i in range(1, len(arr)):
max_current = max(arri, max_current + arri)
if max_current > max_global:
max_global = max_current
return max_global, subsequence
if __name__ == '__main__':
fptr = open(os.environ'OUTPUT_PATH', 'w')
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = maxSubarray(arr)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
メモ
https://www.youtube.com/watch?v=86CQq3pKSUw
https://scrapbox.io/files/61d256f628f4e700218b31cb.png
提出
code: python
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'maxSubarray' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts INTEGER_ARRAY arr as parameter.
#
def maxSubarray(arr):
# Write your code here
suba = 0
subs = 0
for i in arr:
if i > 0:
subs += i
return suba, subs if subs > 0 else max(arr)
if __name__ == '__main__':
fptr = open(os.environ'OUTPUT_PATH', 'w')
t = int(input().strip())
for t_itr in range(t):
n = int(input().strip())
arr = list(map(int, input().rstrip().split()))
result = maxSubarray(arr)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()